package merge;

import java.util.*;

public class Solution {
    public int[][] merge(int[][] intervals) {
        // 差分数组
//        int max = 0;
//        for (int i = 0; i < intervals.length; i++) {
//            max = Math.max(max,intervals[i][1]);
//        }
//        int[] cnt = new int[max+1];
//        for (int[] interval: intervals) {
//            cnt[interval[0]]++;
//            cnt[interval[1]+1]--;
//        }
//        for (int i = 1; i < cnt.length; i++) {
//            cnt[i] = cnt[i-1] + cnt[i];
//        }
//      //  System.out.println(Arrays.toString(cnt));
//        List<int[]> ans = new ArrayList<>();
//   //     int i = 0,j=0;
////        while (i<max&&j<=max) {
////            while (i<max&&cnt[i] == 0)i++;
////            j = i;
////            while (j<=max&&cnt[j+1]>0)j++;
////            ans.add(new int[]{i,j});
////            i = j+1;
////        }
//        return ans.toArray(new int[ans.size()][]);

        // 合并区间
        // 贪心 先排序
        LinkedList<int[]> ans = new LinkedList<>();
        Arrays.sort(intervals, (o1, o2) -> o1[0] - o2[0]);
        ans.addLast(intervals[0]);
        for (int i = 1; i < intervals.length; i++) {
            if(intervals[i][0]<= ans.peekLast()[1]){
                ans.peekLast()[1] = Math.max(ans.peekLast()[1],intervals[i][1]);
            }else {
                ans.addLast(intervals[i]);
            }
        }
        return ans.toArray(new int[ans.size()][]);
    }
}
